Sequential Digits¶
Time: O(1); Space: O(1); medium
An integer has sequential digits if and only if each digit in the number is one more than the previous digit.
Return a sorted list of all the integers in the range [low, high] inclusive that have sequential digits.
Example 1:
Input: low = 100, high = 300
Output: [123,234]
Example 2:
Input: low = 1000, high = 13000
Output: [1234,2345,3456,4567,5678,6789,12345]
Notes:
10 <= low <= high <= 10^9
1. Backtracking¶
Intuition There are totally (9 + 8 + … + 1) = (10) * 9 / 2 = 45 solutions. So we could list all possible solutions and count the result.
[3]:
class Solution1(object):
def sequentialDigits(self, low, high):
"""
:type low: int
:type high: int
:rtype: List[int]
"""
base = '123456789'
ans = []
for length in range(2, 10):
for start in range(len(base) - length + 1):
tmp = int(base[start: start + length])
if low <= tmp <= high:
ans.append(tmp)
return ans
[4]:
s = Solution1()
low = 100
high = 300
assert s.sequentialDigits(low, high) == [123,234]
low = 1000
high = 13000
assert s.sequentialDigits(low, high) == [1234,2345,3456,4567,5678,6789,12345]
[5]:
import collections
class Solution2(object):
"""
Time: O((8 + 1) * 8 / 2) = O(1)
Space: O(8) = O(1)
"""
def sequentialDigits(self, low, high):
"""
:type low: int
:type high: int
:rtype: List[int]
"""
result = []
q = collections.deque(range(1, 9))
while q:
num = q.popleft()
if num > high:
continue
if low <= num:
result.append(num)
if num%10+1 < 10:
q.append(num*10+num%10+1)
return result
[6]:
s = Solution2()
low = 100
high = 300
assert s.sequentialDigits(low, high) == [123,234]
low = 1000
high = 13000
assert s.sequentialDigits(low, high) == [1234,2345,3456,4567,5678,6789,12345]